|
課程名稱 |
整數與組合最佳化
Integer and Combinatorial Optimization |
|
開課學期 |
102-2 |
|
授課對象 |
工學院 機械工程學研究所 |
|
授課教師 |
黃奎隆 |
|
課號 |
IE7020 |
|
課程識別碼 |
546 M6040 |
|
班次 |
|
|
學分 |
3 |
|
全/半年 |
半年 |
|
必/選修 |
選修 |
|
上課時間 |
星期三2,3,4(9:10~12:10) |
|
上課地點 |
國青233 |
|
備註 |
總人數上限：20人 |
|
Ceiba 課程網頁 |
http://ceiba.ntu.edu.tw/1022IE7020_ |
|
課程簡介影片 |
|
|
核心能力關聯 |
核心能力與課程規劃關聯圖 |
|
課程大綱
|
|
為確保您我的權利,請尊重智慧財產權及不得非法影印
|
|
課程概述 |
The course covers fundamental integer programming techniques, including cutting plane methods, branch-and-bound enumeration, Bender’s decomposition, Lagrangain relaxation/decomposition, and heuristic/meta-heuristic programming. It also covers special techniques for solving well-known combinatorial problems, such as knapsack problem and the set covering/partition problem. |
|
課程目標 |
The course primarily focuses on study of Integer Programming and gives an overview of classical methods about problem formulations and solving. The goal of this course is to provide students some understanding such as why some problems are difficult to solve, how they can be reformulated to yield better results, and how effective different algorithms can be. |
|
課程要求 |
Your grade in the course will be determined by homework (25%), midterm exam (25%), final exam (30%) and project (20%). The requirements in details are described as follows:
(83dc) Homework will be assigned every two weeks and the assignments need to be done independently. Late submissions are not accepted except a prior approval is received from the instructor.
(83dc) There are one midterm and one final exam.
(83dc) There is a final project which helps students comprehend the class material and apply them to practical problems or real cases. The project may consist of a literature review for an application area, a research problem, or a computational study. 2 to 3 students (may vary upon the class size) form a group. Prepare a 20-min presentation and submit a report in the last class.
|
|
預期每週課後學習時數 |
|
|
Office Hours |
|
|
指定閱讀 |
|
|
參考書目 |
H.M. Salkin and K. Mathur, Foundations of Integer Programming, North-Holland, New York, 1989
G.L. Nemhauser and L.A. Wolsey, Integer and Combinatorial Optimization, Wiley 1988.
L.A. Wolsey, Integer Programming, Wiley 1998.
|
|
評量方式
(僅供參考) |
|
|
週次 |
日期 |
單元主題 |
|
第1週 |
2/19 |
Introduction |
|
第2週 |
2/26 |
Review of Linear Programming |
|
第3週 |
3/05 |
Modeling and Models |
|
第4週 |
3/12 |
Model Transformation |
|
第5週 |
3/19 |
Dual Fractional IP |
|
第6週 |
3/26 |
Dual Fractional Mixed Integer Programming |
|
第7週 |
4/02 |
Study Day |
|
第8週 |
4/09 |
Dual All-Integer IP |
|
第9週 |
4/16 |
Midterm |
|
第10週 |
4/23 |
Branch and Bound |
|
第11週 |
4/30 |
Search enumeration |
|
第12週 |
5/07 |
Largangian relaxation |
|
第13週 |
5/14 |
Bender decomposition |
|
第14週 |
5/21 |
Knapsack problem |
|
第15週 |
5/28 |
Covering and Partitioning |
|
第16週 |
6/04 |
Traveling Salesman Problem |
|
第17週 |
6/11 |
Project Presentation |
|